package com.study.algorithm;

/**
 * Created by zc on 2017/3/15.
 * 排序
 */
public class NumberSort {
    public static void main(String[] args) {
        int[] arr = {14, 1, 5, 13, 8, 2, 9, 0, 3, 4, 12, 7, 6, 11, 10};
        int[] arr_1;
//        arr_1 = bubbleSort(arr);
//        arr_1 = selectionSort(arr);
        arr_1 = insertSort(arr);
        for (int i : arr_1) {
            System.out.print(i + " ");
        }


    }

    /**
     * 冒泡排序基本概念是：
     * 依次比较相邻的两个数，将小数放在前面，大数放在后面。
     * 即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。
     * 然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，
     * 直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，
     * 将最大的数放到了最后。在第二趟：仍从第一对数开始比较
     * （因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），
     * 将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），
     * 第二趟结束，在倒数第二的位置上得到一个新的最大数
     * （其实在整个数列中是第二大的数）。
     * 如此下去，重复以上过程，直至最终完成排序。
     */
    public static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {//由于后面比较的是arr[j]和arr[j+1]，所以这里i<arr.length-1即可
            for (int j = 0; j < arr.length - i - 1; j++) {
                /**
                 * 如果前者大于后者，交换前后数值
                 */
                if (arr[j] > arr[j + 1]) {
                    arr[j] = arr[j] ^ arr[j + 1];
                    arr[j + 1] = arr[j] ^ arr[j + 1];
                    arr[j] = arr[j] ^ arr[j + 1];
                }
            }
        }
        return arr;
    }

    /**
     * 选择排序基本思路：
     * 把第一个元素依次和后面的所有元素进行比较。
     * 第一次结束后，就会有最小值出现在最前面。
     * 依次类推
     */
    public static int[] selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    arr[i] = arr[i] ^ arr[j];
                    arr[j] = arr[i] ^ arr[j];
                    arr[i] = arr[i] ^ arr[j];
                }
            }
        }
        return arr;
    }

    /**
     * 插入排序基本思想
     * 将n个元素的数列分为已有序和无序两个部分，如插入排序过程示例下所示：
     * {{a1}，{a2，a3，a4，…，an}}
     * {{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}
     * {{a1(n-1），a2(n-1) ，…},{an(n-1)}}
     * 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，
     * 找出插入位置，将该元素插入到有序数列的合适位置中。
     */
    public static int[] insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                arr[j] = arr[j] ^ arr[j - 1];
                arr[j - 1] = arr[j] ^ arr[j - 1];
                arr[j] = arr[j] ^ arr[j - 1];
            }
            /*for (int j = i; j > 0; j--) {//效果和上面的相同
                if (arr[j] < arr[j - 1]) {
                    arr[j] = arr[j] ^ arr[j - 1];
                    arr[j - 1] = arr[j] ^ arr[j - 1];
                    arr[j] = arr[j] ^ arr[j - 1];
                }
            }*/
        }
        return arr;
    }
}
